/*
 * All Rights Reserved.
 *
 * Author : Madhur Raj
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include "structs.h"
#include "readfile.h"

/* Forward declarations */
extern void readfile();

Node *front, *tail;

Node* getListNode ()
{
   Node *newNode = (Node*)malloc(sizeof(Node));
   if (front == NULL)
   {
      front = tail = newNode;
      newNode->next = newNode->prev = NULL;
   }
   else
   {
      tail->next = newNode;
      newNode->prev = tail;
      tail = newNode;
   }

   return (newNode);
}

int* getNode()
{
   Node *newNode = getListNode();

   return (&(newNode->data));
}

void printNodes()
{
   Node *tmp = front;

   while(tmp)
   {
      printf("%d\n", tmp->data);
      tmp = tmp->next;
   }
}

void insertionSortRev()
{
    Node *tmp, *tmp1, *tmp2;
    int  curr;

    for(tmp=front->next; tmp; tmp=tmp->next)
    {
       curr = tmp->data;
       tmp2 = tmp;
       tmp1 = tmp->prev;
       do
       {
          if (tmp1->data < curr)
          {
             SWAP(&tmp1->data, &tmp1->next->data);
             tmp2 = tmp1;
             tmp1 = tmp1->prev;
             if (!tmp1)
                break;
          }
          else
          {
             break;
          }
       }while(1);
       tmp2->data = curr;
    }
}

void insertionSort()
{
    Node *tmp, *tmp1, *tmp2;
    int  curr;

    for(tmp=front->next; tmp; tmp=tmp->next)
    {
       curr = tmp->data;
       tmp2 = tmp;
       tmp1 = tmp->prev;
       do
       {
          if (tmp1->data > curr)
          {
             SWAP(&tmp1->data, &tmp1->next->data);
             tmp2 = tmp1;
             tmp1 = tmp1->prev;
             if (!tmp1)
                break;
          }
          else
          {
             break;
          }
       }while(1);
       tmp2->data = curr;
    }
}

void printResult()
{
   FILE *fp;
   Node *tmp;

   fp = fopen("output.txt", "w+");
   if (!fp)
   {
      printf("Unable to open file\n");
      exit(0);
   }

   tmp = front;
   while (tmp)
   {
      fprintf(fp, "%d ", tmp->data);
      tmp = tmp->next;
   }
   fclose(fp);
}

int main()
{
   struct timeval start, finish;
   int count = COUNT;
   front = tail = NULL;
   readfile();
   gettimeofday(&start, NULL);
   do
   {
      insertionSort();
      insertionSortRev();
   } while(--count);
   gettimeofday(&finish, NULL);
   printTime(&start, &finish);
    
   printResult();
#ifdef DEBUG
   printNodes();
#endif
   return(0);
}
